/*
 * =====================================================================================
 *
 *       Filename:  CStack.h
 *
 *    Description:  CStack.h
 *
 *         Author:  Younghyun Jo
 *   Organization:  Master Student
 *                  Computer Systems and Platforms Laboratory
 *                  Department of Computer Science and Engineering
 *                  Seoul National University
 *
 * =====================================================================================
 */

#include <sys/time.h>
#include <pthread.h>

#define item_t unsigned long

class Node {
  public:
    Node();
    Node(const item_t value);
    ~Node(void);

    const item_t _value;
    Node* _next;
    Node* _prev;
};

class CStack {
  public:
    CStack();
    virtual ~CStack(void);

    virtual bool   Push(int value, int thread_id);
    virtual Node*  Pop(int thread_id);
    virtual Node*  Peek(void);

    unsigned long failures = 0;

  protected:
    Node* _head; // point to start of the stack
    Node* _top; // point to top of the stack
};

//--------------------------------------------------------------------------------------
// CCoarseGrainedLockStack, CLockFreeStack
//

#define lock_init(lock) pthread_mutex_init(lock, NULL)
#define lock_destruct(lock) pthread_mutex_destroy(lock)
#define lock_acquire pthread_mutex_lock
#define lock_release pthread_mutex_unlock
#define lock_t pthread_mutex_t

class CCoarseGrainedLockStack : public CStack {
  public:
    CCoarseGrainedLockStack();
    virtual ~CCoarseGrainedLockStack(void);

    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

  protected:
    lock_t _lock; // the coarse grained lock
                  // on Tilera, it is actually tmc_spin_mutex_t
                  // tmc_spin_mutex_t is a basic spin lock built-in
};

class CTransactionalMemory : public CStack {
  public:
    CTransactionalMemory();
    virtual ~CTransactionalMemory(void);
    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

  protected:
};

class CCoarseGrainedTransactionalMemory : public CStack {
  public:
    CCoarseGrainedTransactionalMemory();
    virtual ~CCoarseGrainedTransactionalMemory(void);
    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

    bool LockPush(int value, int thread_id);
    Node* LockPop(int thread_id);

  protected:
    lock_t _lock; // the coarse grained lock
};

class CLockFreeStack : public CStack {
  public:
    CLockFreeStack();
    virtual ~CLockFreeStack(void);

    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

  protected:
};

class CLockFreeTransactionalMemory : public CStack {
  public:
    CLockFreeTransactionalMemory();
    virtual ~CLockFreeTransactionalMemory();

    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

  protected:
};

//--------------------------------------------------------------------------------------
// CEliminationBackoffStack
//

#define EMPTY 0
#define WAITING 1
#define BUSY 2
#define NOITEM 0

// it just send TimeoutException signal
class TimeoutException {
  public:
    TimeoutException() {}
    ~TimeoutException() {}
};

class CTimeUnit {
  public:
    long long GetTimeStamp(void); // return the system time
};

class CRandom {
  public:
    CRandom() { srand((unsigned)NULL); }
    
    int nextInt(int range) {
      return rand()%range;
    }
};

class CRangePolicy {
  public:
    CRangePolicy(int range);
    ~CRangePolicy();

    int GetRange();
    void RecordEliminationSuccess();
    void RecordEliminationTimeout();

  private:
    int _range; // the number of range size for elimination array
    unsigned long _success; // the number of elimination backoff successes
    unsigned long _timeout; // the number of elimination backoff timeouts
};

// it mimics the AtomicStampedReference functionality in JAVA
class CAtomicStampedReference {
  public:
    CAtomicStampedReference();
    ~CAtomicStampedReference();

    bool CompareAndSet(item_t yrItem, item_t myItem, int beforeState, int nextState);
    item_t Get(int* stampHolder);
    void Set(item_t item, int newStamp);

  private:
    item_t _item;
    //int _state; // state = { EMPTY, WAITING, BUSY }
                  // state is actually 3 bits, and it is located in
                  // [63:62] bits in _item's Virtual Address
};

class CLockFreeExchanger {
  public:
    CLockFreeExchanger();
    ~CLockFreeExchanger();

    item_t Exchange(item_t myItem, long long timeout, CTimeUnit* unit);

  private:
    CAtomicStampedReference* _slot;
};

class CEliminationArray {
  public:
    CEliminationArray(int capacity, long long timeout);
    ~CEliminationArray();

    CLockFreeExchanger** exchanger;
    item_t visit(item_t node, int range);

  private:
    CRandom* _random;
    CTimeUnit* _timeUnit;
    long long _duration;
    int _capacity;
};

class CEliminationBackoffStack : public CStack {
  public:
    CEliminationBackoffStack();
    CEliminationBackoffStack(int capacity, long long timeout); // explicit capacity
    virtual ~CEliminationBackoffStack(void);

    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

  protected:

  private:
    CEliminationArray* _eliminationArray;
    CRangePolicy* _rangePolicy; // range policy
    int _capacity; // capacity for the elimination array
    long long _timeout; // timeout value for the elimination array
};

////////////////////////////////////
// CEliminationBackoffTransactionalMemory

class CEliminationBackoffTransactionalMemory : public CStack {
  public:
    CEliminationBackoffTransactionalMemory();
    CEliminationBackoffTransactionalMemory(int capacity, long long timeout); // explicit capacity
    virtual ~CEliminationBackoffTransactionalMemory(void);

    virtual bool  Push(int value, int thread_id);
    virtual Node* Pop(int thread_id);

  protected:

  private:
    CEliminationArray* _eliminationArray;
    CRangePolicy* _rangePolicy; // range policy
    int _capacity; // capacity for the elimination array
    long long _timeout; // timeout value for the elimination array
};

